package org.example.myleet.rosalind.pper;

public class Solution {

    private static int MOD_BASE = 1000000;

    private int[][] memo;

    //部分排列数（从n个元素中取出k个数并进行排列的总数）：P(n, k) = n * (n - 1) * ... * (n - k + 1)
    public void printPartialPermutationNumberTail(int n, int k) {
        int res = 1;
        for (int i = n; i >= n - k + 1; --i) {
            res *= i;
            res %= MOD_BASE;
        }
        System.out.println(res);
    }

    //组合数递推公式：C(n, k) = C(n-1, k-1) + C(n-1, k)
    public void printCombinationNumberTail(int n, int k) {
        memo = new int[n + 1][n + 1];
        int res = getCombinationNumberTail(n - 1, k - 1) + getCombinationNumberTail(n - 1, k);
        System.out.println(res % MOD_BASE);
    }

    private int getCombinationNumberTail(int n, int k) {
        if (k == 0 || n == k) {
            return 1;
        }
        if (n < k) {
            throw new IllegalStateException("n cannot be smaller than k");
        }
        if (0 < memo[n][k]) {
            return memo[n][k];
        }
        int res = getCombinationNumberTail(n - 1, k - 1) + getCombinationNumberTail(n - 1, k);
        memo[n][k] = res;
        return res % MOD_BASE;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
//        solution.printCombinationNumberTail(3, 2);
//        solution.printCombinationNumberTail(10, 3);
//        solution.printCombinationNumberTail(20, 7);
//        solution.printCombinationNumberTail(20, 6);
//        solution.printCombinationNumberTail(21, 7);
        solution.printPartialPermutationNumberTail(21, 7);
        solution.printPartialPermutationNumberTail(100, 9);
    }
}
